这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 上 。 表示包含转移的子串数量，很容易列出转移式：
SP8222 NSUBSTR - Substrings
不难发现到f[i]就是长度为 i 子串的 ∣endpos∣ 的最大值。
根据一个性质后缀自动机的一个点的 endpos 被他的后继分为了很多部分，所以我们可以用parent树dp，处理出它的∣endpos∣。
接着是统计答案，显然我们可以用线段树覆盖。
P3195 [HNOI2008]玩具装箱TOY
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式：
设 sum 为 c 的前缀和，则有
CF321E Ciel and Gondolas
各位大佬都用的 wqs 二分，蒟蒻介绍一种简单方法。
dp 式很好列:
P3503 [POI2010]KLO-Blocks
首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 k 。
进一步可以发现这是一个充要条件。因为大于 k 的数一定能填补到小于 k 的数。
记一个合法的区间为 [l,r] ，sum 为 a 的前缀和。
P4555 [国家集训队]最长双回文串
显然是一道回文自动机板题。
设 L[i] 表示以 i 号点为左端点的最长回文串 ， R[i] 表示以 i 号点为右端点的最长回文串。
L[i] 可以通过将回文串倒过来建自动机求得 ， R[i] 可以直接用原回文串建自动机求得。
0%